// 解题思路：
// 有 n 个活动，给出每个活动的开始和结束时间，看最少需要几个主持人
// 首先需要按照活动的开始时间排序所有的活动
// 将活动按照主持人分组，第一个活动需要一个主持人
// 遍历后续的每个活动，同时去查找前面的组，如果这个活动的开始时间，大于等于前面组里面的活动的结束时间，那么该组的主持人 可以继续主持这个活动
// 如果该活动的开始时间小于前面所有组里活动的结束时间，那么这个活动还需要一名新的主持人，再开一个新的组
// 最后返回组的数量即可

// 优化：
// 但是一个新的活动，查找前面组里的活动的结束时间，需要遍历每一个组，这就超时了
// 因此，需要使用小根堆来进行优化
// 小根堆只需要存前面活动结束的时间即可
// 新的活动的开始时间如果比最早结束的活动的结束时间还早，那就将这个活动的结束时间也存在小根堆里，表示一个新的组
// 如果新活动的开始时间比最早结束的活动的时间晚或者相同，那么就将这个活动的结束时间代替原来活动的结束时间，放在小根堆里
// 这样查找每一个霍活动的时间复杂度就降低为 log(N)

import java.util.*;

public class HostScheduling {
    public int minmumNumberOfHost (int n, int[][] startEnd) {
        Arrays.sort(startEnd, (a, b) -> {
            if(a[0] > b[0]) return 1;
            else if(a[0] < b[0]) return -1;
            return 0;
        });
        PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> {
            if(a > b) return 1;
            else if(a < b) return -1;
            return 0;
        });
        heap.offer(startEnd[0][1]);
        for(int i = 1; i < n; i++){
            int start = startEnd[i][0];
            int end = startEnd[i][1];
            int prevEnd = heap.peek();
            if(start >= prevEnd) {
                heap.poll();
                heap.offer(end);
            } else {
                heap.offer(end);
            }
        }
        return heap.size();
    }
}
